package com.damin;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        shuffle(nums);
        logger.info("打乱后的数组：{}", JSON.toJSONString(nums));
        sort(nums, 0, nums.length - 1);
    }

    protected void sort(T[] nums, int l, int h) {
        if (h <= l)
            return;
        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }

    private int partition(T[] nums, int low, int high) {
        int i = low, j = high + 1;
        T pivot = nums[low];
        while (true) {
            while (less(nums[++i], pivot) && i != high);
            while (less(pivot, nums[--j]) && j != low);
            if (i >= j)
                break;
            swap(nums, i, j);
        }
        swap(nums, low, j);
        return j;
    }

    private void shuffle(T[] nums) {
        List list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }
}
